public class LCS1 {
    // 最长公共子串
    // https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public String LCS1 (String str1, String str2) {
        // write code here
        // 状态表示：dp[i][j]表示以str1第i个位置为结尾的子串和以str2第j个位置为结尾的
        // 最长公共子串
        // 状态转移方程：同样还是根据最后一个位置来推导
        // 如果s1[i] == s2[j]，那么dp[i][j]= dp[i-1][j-1] + str1[i]
        // 否则dp[i][j] = ""
        char[] ch1 = (" " + str1).toCharArray();
        char[] ch2 = (" " + str2).toCharArray();
        String[][] dp = new String[ch1.length][ch2.length];
        // 初始化：
        // dp[0][j]表示以str1第0个位置为结尾，str2第j个位置为结尾的最长公共子串，为" "
        // dp[i][0]同样也是如何，但是为了初始化不影响后面填表的结果，将其初始化为""
        for (int j = 0; j < ch2.length; j++) dp[0][j] = "";
        for (int i = 0; i < ch1.length; i++) dp[i][0] = "";
        String ret = "";
        for (int i = 1; i < ch1.length; i++) {
            for (int j = 1; j < ch2.length; j++) {
                if (ch1[i] == ch2[j]) {
                    dp[i][j] = dp[i-1][j-1] + ch1[i];
                } else {
                    dp[i][j] = "";
                }
                if (dp[i][j].length() > ret.length()) {
                    ret = dp[i][j];
                }
            }
        }
        return ret;
    }

    /**
     * 空间优化，因为在填dp[i][j]的时候，只需要用到dp[i-1][j-1]，也就是一行数据
     * 所以我们可以将其空间有华为一维数组，但是如果我们还是从左到右填表的话，那么dp[j-1]就会被覆盖
     * 所以我们的填表顺序为从上到下，从右往左
     * @param str1
     * @param str2
     * @return
     */
    public String LCS (String str1, String str2) {
        // write code here
        // 状态表示：dp[i][j]表示以str1第i个位置为结尾的子串和以str2第j个位置为结尾的
        // 最长公共子串
        // 状态转移方程：同样还是根据最后一个位置来推导
        // 如果s1[i] == s2[j]，那么dp[i][j]= dp[i-1][j-1] + str1[i]
        // 否则dp[i][j] = ""
        char[] ch1 = (" " + str1).toCharArray();
        char[] ch2 = (" " + str2).toCharArray();
        String[] dp = new String[ch2.length];
        // 初始化：
        // dp[0][j]表示以str1第0个位置为结尾，str2第j个位置为结尾的最长公共子串，为" "
        // dp[i][0]同样也是如何，但是为了初始化不影响后面填表的结果，将其初始化为""
        for (int j = 0; j < ch2.length; j++) dp[j] = "";
        String ret = "";
        for (int i = 1; i < ch1.length; i++) {
            for (int j = ch2.length-1; j>= 0; j--) {
                if (ch1[i] == ch2[j]) {
                    dp[j] = dp[j-1] + ch1[i];
                } else {
                    dp[j] = "";
                }
                if (dp[j].length() > ret.length()) {
                    ret = dp[j];
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        LCS1 lcs = new LCS1();
        System.out.println(lcs.LCS("22222","22222"));
    }
}
